#![allow(dead_code, mutable_transmutes, non_camel_case_types, non_snake_case, non_upper_case_globals, unused_assignments, unused_mut)]
use std::mem;
use crate::alloc_testing::*;
extern "C" {
            }
pub type size_t = libc::c_ulong;
pub type BinaryHeapType = libc::c_uint;
pub const BINARY_HEAP_TYPE_MAX: BinaryHeapType = 1;
pub const BINARY_HEAP_TYPE_MIN: BinaryHeapType = 0;
pub type BinaryHeapValue = *mut libc::c_void;
pub type BinaryHeapCompareFunc = Option::<
    unsafe extern "C" fn(BinaryHeapValue, BinaryHeapValue) -> libc::c_int,
>;
#[derive(Copy, Clone)]
#[repr(C)]
pub struct _BinaryHeap {
    pub heap_type: BinaryHeapType,
    pub values: *mut BinaryHeapValue,
    pub num_values: libc::c_uint,
    pub alloced_size: libc::c_uint,
    pub compare_func: BinaryHeapCompareFunc,
}
pub type BinaryHeap = _BinaryHeap;
extern "C" fn binary_heap_cmp(
    mut heap: *mut BinaryHeap,
    mut data1: BinaryHeapValue,
    mut data2: BinaryHeapValue,
) -> libc::c_int {
    let boxed_heap = unsafe { Box::from_raw(heap) };
    let heap_type = boxed_heap.heap_type;
    let compare_func = boxed_heap.compare_func.expect("non-null function pointer");

    let result = if heap_type as libc::c_uint == BINARY_HEAP_TYPE_MIN as libc::c_int as libc::c_uint {
        unsafe { compare_func(data1, data2) }
    } else {
        -unsafe { compare_func(data1, data2) }
    };

    heap = Box::into_raw(boxed_heap);
    result
}
#[no_mangle]
pub extern "C" fn binary_heap_new(
    mut heap_type: BinaryHeapType,
    mut compare_func: BinaryHeapCompareFunc,
) -> *mut BinaryHeap {
    let heap: *mut BinaryHeap = unsafe {
        alloc_test_malloc(std::mem::size_of::<BinaryHeap>() as libc::c_ulong) as *mut BinaryHeap
    };
    if heap.is_null() {
        return std::ptr::null_mut();
    }

    let mut boxed_heap = unsafe { Box::from_raw(heap) };
    boxed_heap.heap_type = heap_type;
    boxed_heap.num_values = 0;
    boxed_heap.compare_func = compare_func;
    boxed_heap.alloced_size = 16;

    boxed_heap.values = unsafe {
        alloc_test_malloc(
            (std::mem::size_of::<BinaryHeapValue>() as libc::c_ulong)
                .wrapping_mul(boxed_heap.alloced_size as libc::c_ulong),
        ) as *mut BinaryHeapValue
    };

    if boxed_heap.values.is_null() {
        alloc_test_free(heap as *mut libc::c_void);
        return std::ptr::null_mut();
    }

    let heap = Box::into_raw(boxed_heap);
    heap
}
#[no_mangle]
pub extern "C" fn binary_heap_free(mut heap: *mut BinaryHeap) {
    if !heap.is_null() {
        let boxed_heap = unsafe { Box::from_raw(heap) };
        alloc_test_free(boxed_heap.values as *mut libc::c_void);
        alloc_test_free(heap as *mut libc::c_void);
        let heap = Box::into_raw(boxed_heap);
    }
}
#[no_mangle]
pub extern "C" fn binary_heap_insert(
    mut heap: *mut BinaryHeap,
    mut value: BinaryHeapValue,
) -> libc::c_int {
    let mut new_values: *mut BinaryHeapValue = std::ptr::null_mut();
    let mut index: libc::c_uint = 0;
    let mut new_size: libc::c_uint = 0;
    let mut parent: libc::c_uint = 0;

    let mut boxed_heap = unsafe { Box::from_raw(heap) };

    if boxed_heap.num_values >= boxed_heap.alloced_size {
        new_size = boxed_heap.alloced_size.wrapping_mul(2);
        new_values = unsafe {
            alloc_test_realloc(
                boxed_heap.values as *mut libc::c_void,
                (std::mem::size_of::<BinaryHeapValue>() as libc::c_ulong)
                    .wrapping_mul(new_size as libc::c_ulong),
            ) as *mut BinaryHeapValue
        };
        if new_values.is_null() {
            heap = Box::into_raw(boxed_heap);
            return 0;
        }
        boxed_heap.alloced_size = new_size;
        boxed_heap.values = new_values;
    }
    index = boxed_heap.num_values;
    boxed_heap.num_values = boxed_heap.num_values.wrapping_add(1);

    while index > 0 {
        parent = index.wrapping_sub(1).wrapping_div(2);

        if unsafe { binary_heap_cmp(heap, *boxed_heap.values.offset(parent as isize), value) < 0 } {
            break;
        }
        unsafe {
            *boxed_heap.values.offset(index as isize) = *boxed_heap.values.offset(parent as isize);
        }
        index = parent;
    }

    unsafe {
        *boxed_heap.values.offset(index as isize) = value;
    }
    heap = Box::into_raw(boxed_heap);
    return 1;
}
#[no_mangle]
pub extern "C" fn binary_heap_pop(mut heap: *mut BinaryHeap) -> BinaryHeapValue {
    let mut result: BinaryHeapValue = std::ptr::null_mut();
    let mut new_value: BinaryHeapValue = std::ptr::null_mut();
    let mut index: libc::c_uint = 0;
    let mut next_index: libc::c_uint = 0;
    let mut child1: libc::c_uint = 0;
    let mut child2: libc::c_uint = 0;

    let mut boxed_heap = unsafe { Box::from_raw(heap) };

    if boxed_heap.num_values == 0 {
        heap = Box::into_raw(boxed_heap);
        return std::ptr::null_mut();
    }

    result = unsafe { *boxed_heap.values.offset(0) };
    new_value = unsafe { *boxed_heap.values.offset((boxed_heap.num_values).wrapping_sub(1) as isize) };
    boxed_heap.num_values = (boxed_heap.num_values).wrapping_sub(1);
    index = 0;

    loop {
        child1 = index.wrapping_mul(2).wrapping_add(1);
        child2 = index.wrapping_mul(2).wrapping_add(2);

        if child1 < boxed_heap.num_values && binary_heap_cmp(heap, new_value, unsafe { *boxed_heap.values.offset(child1 as isize) }) > 0 {
            if child2 < boxed_heap.num_values && binary_heap_cmp(heap, unsafe { *boxed_heap.values.offset(child1 as isize) }, unsafe { *boxed_heap.values.offset(child2 as isize) }) > 0 {
                next_index = child2;
            } else {
                next_index = child1;
            }
        } else if child2 < boxed_heap.num_values && binary_heap_cmp(heap, new_value, unsafe { *boxed_heap.values.offset(child2 as isize) }) > 0 {
            next_index = child2;
        } else {
            unsafe { *boxed_heap.values.offset(index as isize) = new_value };
            heap = Box::into_raw(boxed_heap);
            return result;
        }

        unsafe { *boxed_heap.values.offset(index as isize) = *boxed_heap.values.offset(next_index as isize) };
        index = next_index;
    }
}
#[no_mangle]
pub extern "C" fn binary_heap_num_entries(
    mut heap: *mut BinaryHeap,
) -> libc::c_uint {
    let boxed_heap = unsafe { Box::from_raw(heap) };
    let num_values = boxed_heap.num_values;
    let heap = Box::into_raw(boxed_heap);
    num_values
}
